#include "declare.hpp"

// 插入排序
std::vector<Node>& MapSystem::_InsertSort_Implement()
{
    for (size_t i = 1; i < _vector_array.size(); ++i)
    {
        Node temp = _vector_array[i];
        size_t j = i;
        while (j > 0 && _vector_array[j - 1]._ulLinkID > temp._ulLinkID)
        {
            _vector_array[j] = _vector_array[j - 1];
            --j;
        }
        _vector_array[j] = temp;
    }
    return _vector_array; // 返回排序后的数组引用
}

// 希尔排序
std::vector<Node>& MapSystem::_ShellSort_Implement()
{
    for (size_t gap = _vector_array.size() / 2; gap > 0; gap /= 2)
    {
        for (size_t i = gap; i < _vector_array.size(); ++i)
        {
            Node temp = _vector_array[i];
            size_t j = i;
            while (j >= gap && _vector_array[j - gap]._ulLinkID > temp._ulLinkID)
            {
                _vector_array[j] = _vector_array[j - gap];
                j -= gap;
            }
            _vector_array[j] = temp;
        }
    }
    return _vector_array; // 返回排序后的数组引用
}

// 选择排序
std::vector<Node>& MapSystem::_SelectSort_Implement()
{
    for (size_t i = 0; i < _vector_array.size(); ++i)
    {
        size_t minIndex = i;
        for (size_t j = i + 1; j < _vector_array.size(); ++j)
        {
            if (_vector_array[j]._ulLinkID < _vector_array[minIndex]._ulLinkID)
            {
                minIndex = j;
            }
        }
        std::swap(_vector_array[i], _vector_array[minIndex]);
    }
    return _vector_array; // 返回排序后的数组引用
}

// 冒泡排序
std::vector<Node>& MapSystem::_BubbleSort_Implement()
{
    bool swapped;
    for (size_t i = 0; i < _vector_array.size() - 1; ++i)
    {
        swapped = false;
        for (size_t j = 0; j < _vector_array.size() - i - 1; ++j)
        {
            if (_vector_array[j]._ulLinkID > _vector_array[j + 1]._ulLinkID)
            {
                std::swap(_vector_array[j], _vector_array[j + 1]);
                swapped = true;
            }
        }
        if (!swapped)
            break; // 如果没有交换，说明已经有序，提前结束
    }
    return _vector_array; // 返回排序后的数组引用
}

// 快速排序
std::vector<Node>& MapSystem::_QuickSort_Implement(size_t left, size_t right)
{
    if (left >= right) return _vector_array; // 递归结束条件

    size_t pivotIndex = left + (right - left) / 2;
    Node pivot = _vector_array[pivotIndex];
    std::swap(_vector_array[pivotIndex], _vector_array[right]);

    size_t i = left;
    for (size_t j = left; j < right; ++j)
    {
        if (_vector_array[j]._ulLinkID < pivot._ulLinkID)
        {
            std::swap(_vector_array[i], _vector_array[j]);
            ++i;
        }
    }
    std::swap(_vector_array[i], _vector_array[right]); // 将pivot放到正确位置

    if (i > 0) _QuickSort_Implement(left, i - 1); // 递归排序左半部分
    _QuickSort_Implement(i + 1, right); // 递归排序右半部分

    return _vector_array; // 返回排序后的数组引用
}

// 归并排序
std::vector<Node>& MapSystem::_MergeSort_Implement(size_t left, size_t right)
{
    if (left >= right) return _vector_array; // 递归结束条件

    size_t mid = left + (right - left) / 2;
    _MergeSort_Implement(left, mid); // 递归排序左半部分
    _MergeSort_Implement(mid + 1, right); // 递归排序右半部分

    std::vector<Node> temp(right - left + 1); // 临时数组
    size_t i = left, j = mid + 1, k = 0;

    // 合并
    while (i <= mid && j <= right)
    {
        if (_vector_array[i]._ulLinkID <= _vector_array[j]._ulLinkID)
            temp[k++] = _vector_array[i++];
        else
            temp[k++] = _vector_array[j++];
    }

    while (i <= mid) temp[k++] = _vector_array[i++]; // 复制剩余的左半部分
    while (j <= right) temp[k++] = _vector_array[j++]; // 复制剩余的右半部分

    for (size_t m = 0; m < temp.size(); ++m)
    {
        _vector_array[left + m] = temp[m]; // 更新原数组
    }

    return _vector_array; // 返回排序后的数组引用
}
